// https://www.lintcode.com/problem/tower-of-hanoi/

public class Solution {
    /**
     * @param n: the number of disks
     * @return: the order of moves
     */
    public List<String> towerOfHanoi(int n) {
        // write your code here
        List<String> ret = new ArrayList<>();
        if (n > 0) {
            move(ret, n, 'A', 'C', 'B');
        }
        return ret;
    }

    protected void move(List<String> ret, int n, char from, char to, char by) {
        if (n == 1) {
            ret.add("from " + from + " to " + to);
        } else {
            move(ret, n - 1, from, by, to);
            ret.add("from " + from + " to " + to);
            move(ret, n - 1, by, to, from);
        }
    }
}